This invention relates generally to analysis of mixed integer linear programs (MILPs) and, more specifically, relates to price-and-branch techniques for mixed integer linear programs.
This section is intended to provide a background or context to the invention disclosed below. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived, implemented or described. Therefore, unless otherwise explicitly indicated herein, what is described in this section is not prior art to the description in this application and is not admitted to be prior art by inclusion in this section.
A mixed-integer linear program (MILP) is a problem representing the minimization or maximization of a linear function subject to linear constraints, where a designated set of decision variables are required to take on integer values. These problems are typically represented using a matrix structure, where constraints correspond to rows and columns correspond to decision variables. The optimal solution is a set of values of the decision variables that gives the optimum objective value, which is the minimum or maximum value of the linear function subject to the constraints.
Techniques for mixed integer linear programming have been developed since the 1960s. These MILP problems have many applications and may be solved using computer systems. In fact, there are computer programs made specifically to solve MILP problems. One such solver is called the IBM ILOG CPLEX Optimizer, which is a high-performance mathematical programming solver for solving linear programs, mixed integer programs, and quadratic programs.
One application for MILP is job allocation. For instance, suppose people are being allocated to jobs, and there are many people and many jobs. A typical solver would require all the possible person/job combinations to be given to the solver, with each combination corresponding to a decision variable, and the problem would not be tractable when the number of combinations is large. Even if the problem is tractable, a MILP solver may take a very long time to determine a solution, dependent on the complexity of the linear constraints.
Ideally, one would solve a MILP by presenting all of the decision variables to the MILP solver, but the larger the number of variables, the longer the solution takes to compute (or becomes intractable). In some applications, the number of decision variables may become so large that time criteria are not met and/or the problem is no longer tractable.
Branch-and-price mechanisms have been developed to attempt to reduce solution time and/or make a problem tractable by not representing all of the decision variables to the MILP solver. Branch-and-price is a branch-and-bound method in which at each node of a search tree, columns may be added to a linear program (LP) relaxation. At the start of the algorithm, sets of columns are excluded from the LP relaxation in order to reduce the computational and memory requirements and then columns are added back to the LP relaxation as needed. Prices are determined every time a linear program is solved in between branching. Branching occurs when certain conditions are met. The approach is based on the observation that, for large problems, most columns will have their corresponding variable equal to zero in any optimal solution. Thus, the large majority of the columns are irrelevant for solving the problem.
Current branch-and-price mechanisms do improve solution time, but these mechanisms discard much of the power of the mixed integer programming optimizer.